package C045;

import java.util.Arrays;

/**
 * ClassName: C01
 * Package: C045
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/7 09:07
 * @Version 1.0
 * @Since 1.0
 */
public class C01 {
    public static void main(String[] args) {
/*
[[1, 2, 3, 4, 5], [2, 4, 6, 8], [1, 4, 7, 10]],[[3, 4, 5, 6, 7, 8], [2, 4, 6, 8], [1, 3, 5, 7, 9]]
 */

        int[][] b = {{1, 2, 3, 4, 5}, {2, 4, 6, 8}, {1, 4, 7, 10}};
        int[][] a = {{3, 4, 5, 6, 7, 8},{2, 4, 6, 8}, {1, 3, 5, 7, 9}};
        System.out.println(Arrays.toString(countConsistentKeys(b, a)));
    }

    // 获取个数
    public static int[] countConsistentKeys (int[][] b, int[][] a) {
        // write code here
        // 1. 构建a的前缀树
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            stringBuilder.setLength(0);
            for (int j = 1; j < a[i].length; j++) {
                stringBuilder.append(a[i][j] - a[i][j-1]).append("#");
            }
            insert(stringBuilder.toString());
        }

        // 2 . 统计b的前缀字符的个数
        int[] ans = new int[b.length];
        for (int i = 0; i < b.length; i++) {
            stringBuilder.setLength(0);
            for (int j = 1; j < b[i].length; j++) {
                stringBuilder.append(b[i][j] - b[i][j - 1]).append("#");
            }
            ans[i] = prefixSearch(stringBuilder.toString());
        }

        // 3. 返回结果
        return ans;
    }

    static int MAXLEN = 100000;
    static int[][] ele = new int[MAXLEN][12]; // 考虑负数的情况
    static int cnt = 0;
    static int[] pass = new int[MAXLEN];
    static int[] end = new int[MAXLEN];

    public static int getIndex(char c) {
        if(c == '#') {
            return 11;
        } else if(c == '-') {
            return 10;
        } else {
            return c - '0';
        }
    }

    // 插入元素
    public static void insert(String word) {
        char[] charArray = word.toCharArray();
        pass[0] ++;
        int index, cur = 0;
        for (int i = 0; i < charArray.length; i++) {
            index = getIndex(charArray[i]);
            if (ele[cur][index] == 0) {
                ele[cur][index] = ++cnt;
            }
            cur = ele[cur][index];
            pass[cur] ++;
        }
        end[cur] ++;
    }

    // 查找前缀的个数
    public static int prefixSearch(String word) {
        char[] charArray = word.toCharArray();
        int index, cur = 0;
        for (int i = 0; i < charArray.length; i++) {
            index = getIndex(charArray[i]);
            if(ele[cur][index] == 0) {
                return 0;
            }
            cur = ele[cur][index];
        }
        return pass[cur];
    }

}
